/*
153. 寻找旋转排序数组中的最小值
假设一个按照升序排列的有序数组从某未知的位置旋转。

（比如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2）。

找到其中最小的元素。

你可以假设数组中不存在重复的元素。
*/

class Solution
{
public:
    int findMin(vector<int> &nums)
    {
        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return nums[0];
        if(nums[0] < nums[nums.size() - 1]) return nums[0];
        int high = nums.size() - 1;
        int low = 0;
        int n = high / 2;
        int base = nums[0];
        while(low <= high) {
            if(nums[n] >= base) {
                low = n + 1;
            } else {
                high = n - 1;
            }
            n = low + (high - low) / 2;
        }
        return nums[low];
    }
};